Many modern communication systems involve a number of geographically dispersed transmitter-receivers which communicate with each other by way of a high data rate transmission channel. The transmission channel may be a broadcast channel, fiber optic cable or electromagnetic transmission line, or it may include transmissions among a number of Earth station transmitter-receivers by way of the transponder of an Earth satellite. Economic considerations suggest that when the capital cost of a communications system is large, the capacity (the maximum throughput) of the system be as large as possible. Capacity is at a maximum, or 100%, when a single transmitter operates continuously and uses the communication channel or transmission path to address one or more receivers. Such a path or channel is also known as a bus. When more than one transmitter must use the transmission path, a problem arises relating to scheduling the transmitters for maximum system capacity. If the transmitters which are to share the transmission path are physically near each other, a scheduler may be connected to each transmitter to uniquely establish a transmission time for each transmitter depending upon the amount of data to be transmitted, its importance or like considerations. When the geographic distance between the transmitters is large, and there is therefore a time delay between the signals leaving the scheduler and the time at which they arrive at the transmitters to be controlled, the scheduler may not be efficient in adapting to the changing conditions at each transmitter.
One approach to multi access on such high propagation delay channels is to partition the channel time in a fixed, predetermined manner. Such systems are known as time division multiple access (TDMA) systems. They are efficient when the user population includes a few users having high duty cycles. Many modern systems provide communication among interactive data terminals, which operate in low duty cycle burst modes. Time division multiple access is not efficient in this context.
In response to the increasing need for communication over transmission paths having a time delay, schemes have evolved in which each transmitter-receiver (Tx/Rx) monitors the signal on the transmission path to determine whether the transmission path is active or idle, for scheduling transmissions during idle intervals. Because of the path delays, two or more transmitter-receivers might begin transmission at nearly the same time, unaware of each other's transmission. As a result, the transmission path would carry two or more signals simultaneously, causing a mutual interference known as a collision. Such collisions ordinarily make it impossible to correctly receive and decode the information carried by the signals. When the information is destroyed by a collision, it must be retransmitted. Many procedures or protocols have been devised for monitoring the transmission path and for scheduling transmissions and retransmissions to maximize capacity. Carrier sensing systems of this general sort have capacities in the region of 80%. U.S. Pat. No. 4,234,952 issued Nov. 18, 1980, to Gable, for example, stops or truncates the transmission of an information packet when interference is noted during transmission of that packet. Once a transmission has been in progress for the end-to-end propagation time of the transmission path, all transmitters other than the one transmitting are inhibiting and the transmission is completed without collision.
The problems associated with TDMA and carrier sensing systems have led to contention protocols intended to more efficiently utilize a charged high propagation delay transmission path for low duty cycle communications among large number of users. In general, contention systems allow any transmitter-receiver to transmit a message at will. In the event that two transmitter-receivers transmit at overlapping times, a collision occurs, as in the case of the carrier sensing systems with long propagation delays. Each transmitter-receiver must determine the existence of such collisions and respond by retransmitting the information. The ALOHA contention protocol is an asynchronous or unslotted system in which a plurality of remote stations are connected to a central station by a single transmission path. The various remote stations transmit complete packets of data over the transmission path. Collisions are resolved by retransmission at random times after the collision. The ALOHA system has a capacity of approximately 18 percent for low data rate transmissions. Thus, it has a relatively low maximum throughput due to the inefficiency associated with wasting the time of two transmission packets in the event of a slight overlap of packet transmission times.
Slotted or synchronous ALOHA is an improvement over simple ALOHA in which all transmissions occur in fixed non-overlapping time slots. By thus slotting or synchronizing transmissions, the vulnerable time for packet collision is reduced from a duration equal to two packet intervals to one packet interval, and the capacity therefore increases to 37%. The slotting requirement, however, increases the cost and complexity of the system. Also, both slotted and unslotted ALOHA are subject to further inefficiencies resulting from collisions of retransmitted packets.
A contention access protocol in which new transmissions are prevented from interfering with retransmissions provides up to approximately 49% capacity. This system is the Capetanakis tree algorithm, described in IEEE Transactions on Information Theory, September 1979, pp. 505-515, later refined by J. L. Massey and by R. G. Gallager. Tree algorithms achieve high capacity on short propagation delay systems, but are not well suited to long propagation delay systems because the outcome of a slot transmission must be known before transmission on the next slot can begin.
A slotted contention access system entitled "Announced Retransmission Random Access (ARRA)" is described in U.S. patent application, Ser. No. 873,446, filed June 6, 1986, which is a continuation of Ser. No. 610,007, filed May 14, 1984, now abandoned, both filed in the name of the Raychaudhuri. The ARRA system pre-establishes the time at which a retransmission will occur in the event of a collision in a particular packet, and transmits this information together with the original packet in a manner which survives the collision. Thus, all transmitter-receivers are advised of the time at which retransmission will occur, and are programmed to inhibit transmission during that period. The ARRA system provides a capacity of approximately 53% for the less complex embodiments and as high as 60% in the more complex embodiments.
For some applications, the slotting or synchronization requirement of slotted ALOHA, Tree Algorithm Random Access or ARRA may be undesirable. A contention access communication system is desired which is asynchronous and which provides high capacity.